import numpy as np
"""
定义几个变量的值
data:原来的数据集
property_num:类别号，从1：row（data）-1
"""
def calcEnt(data):
    """
    返回函数的熵，具体不说了
    :param data:
    :return:
    """
    label=np.array([i[-1] for i in data])
    label_num={}
    for lb in label:
        if lb in label_num.keys():
            label_num[lb]=label_num[lb]+1
        else:
            label_num[lb]=1
    sumEnt=0
    for key in label_num.keys():
        num=label.shape[0]
        temp=label_num[key]/num*np.log2(label_num[key]/num)
        sumEnt=sumEnt+temp
    sumEnt=-sumEnt
    return sumEnt
def seperate(data,property_num):
    """
    返回一个某一个属性，依据属性的类别进行排列
    :param data:
    :param property_num:
    :return:
    """
    property_list=[]
    for i in data:
        property_list.append([i[property_num-1],i[-1]])
    seperate_result=[]
    property_list_num=[]
    for i in property_list:
        if i[0] not in property_list_num:
            property_list_num.append(i[0])
    for i in property_list_num:
        new_list=[]
        for j in property_list:
            if j[0]==i:
                new_list.append(j)
        seperate_result.append(new_list)
    return seperate_result
def calcgain(data,property_num):
    """
    返回该分类的gain值
    :param data:
    :param property_num:
    :return:
    """
    sepmat=seperate(data,property_num)
    rownum=len(data)
    sum=0
    for i in sepmat:
        temp=calcEnt(i)
        sum=sum+len(i)/rownum*temp
    gain=calcEnt(data)-sum
    return gain
def classify(data):
    """
    选择最优的分类，返回属性号
    :param data:
    :return:
    """
    max=calcgain(data,1)
    maxi=0
    for i in range(np.shape(data)[-1]-1):
        if calcgain(data,i+1)>max:
            max=calcgain(data,i+1)
            maxi=i+1
    return maxi
def split(data,property_num):
    datasplit=[]
    for i in data:
            if property_num==1:
                former=[]
            else:
                former=i[:property_num-1]
            if property_num==np.shape(data)[-1]:
                follower=[]
            else:
                follower=i[property_num:]
            former.extend(follower)
            datasplit.append(former)
    return datasplit
def mytree(data,labels):
    if calcEnt(data)==0:
        return data
    if len(data[0])==1:
        return True
    bestFeat=classify(data)
    bestFeatlabel=labels[bestFeat-1]
    Tree={bestFeatlabel:{}}
    del labels[bestFeat-1]
    for value in range(len(seperate(data,bestFeat))):
        data=split(data,bestFeat)
        Tree[bestFeatlabel][value]=mytree(data,labels)
    return Tree
data=[[1,1,1,1,1,1,1],[2,1,2,1,1,1,1],[2,1,1,1,1,1,1],[1,1,2,1,1,1,1],[3,1,1,1,1,1,1],[1,2,1,1,2,2,1],[2,2,1,2,2,2,1],[2,2,1,1,2,1,1],[2,2,2,2,2,1,0],[1,3,3,1,3,2,0],[3,3,3,3,3,1,0],[3,1,1,3,3,2,0],[1,2,1,2,1,1,0],[3,2,2,2,1,1,0],[2,2,1,1,2,2,0],[3,1,1,3,3,1,0],[1,1,2,2,2,1,0]]
mytree(data,['A','B','C','D','E','F'])
